Just two questions this week, though the first one has a few parts (shown in the tabs. Don’t miss them!). Question 1 on this problem set is about using lists for tabulation and working with GCompounds. Question 2 is about working with multidimensional arrays. Files are provided in the starting template linked before for both questions. Make sure you fill out the top metadata on each problem please!

Problem 1

A common form of tabulation is that of creating a “histogram”, wherein the different elements of the histogram array represent the counts of how many times a particular value (or range of values) showed up in a certain collection. For example, the first 16 digits of \pi look like:

PI_DIGITS = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 8, 9, 7, 9 ]

If we are dealing with single digits, then there are 10 possible values that we could want to count: the digits 0 through 9. It turns out that these digits map nicely to the index values of an array! So we could store how many times a 0 appears in PI_DIGITS (0 times) in the index 0 element of our histogram, and the number of times the digit 1 appears (2 times) in the index 1 element, and so on. The entire histogram array, once populated, might look like:

showing that there are no 0s, two 1s, one 2, two 3s, etc. in the first sixteen digits of \pi.

Write a function called create_histogram_array(num_2_count, data) which takes two values as arguments:

An integer num_2_count, which represents the number of numbers that you would like to count. You always start your counting at 0. So, for example, num_2_count would have been 10 in our above example, since we were counting 10 different numbers, starting at 0.
A list of integers data, which represents the items for which you would like to tabulate a histogram.

This function should return a new list which has the histogram counts as each element. For example, your function should be able to mimic:

>>> create_histogram_array(5, [1, 0, 3, 2, 4, 2, 2, 1, 3, 0])
[2, 2, 3, 2, 1]

where num_2_count was chosen to be 5 since there were 5 different values appearing in the data list (0 through 4). Note though that if your value of num_2_count is smaller than the variety of digits in data, the later digits should not be counted. Only the first num_2_count digits will be counted. If num_2_count is larger than the number of different digits in data, 0’s will be counted for those extra digits. So, for instance:

>>> create_histogram_array(3, [1, 0, 3, 2, 4, 2, 2, 1, 3, 0])
[2, 2, 3]
>>> create_histogram_array(8, [1, 0, 3, 2, 4, 2, 2, 1, 3, 0])
[2, 2, 3, 2, 1, 0, 0, 0]

Now that you can use your function from Part A to compute a histogram array, how about displaying it nicely to the screen? For this part, write a new function called print_histogram(array) that take a histogram counts list (of the exact sort returned by create_histogram_array!) as an argument. This function should print to the console a horizontal histogram using asterisks to indicate the count of values in each index. For example, if you call print_histogram with the histogram formed by the first 16 digits of \pi, you should see the following:

>>> print_histogram(create_histogram_array(10, PI_DIGITS))
0:
1: **
2: *
3: **
4: *
5: ****
6: *
7: *
8: *
9: ***

Your function should mimic this printing exactly. This should not be particularly complicated, as you have all the necessary tools with string formatting and the repetition operator for strings.

While printing to the console is one way to visualize a histogram, it is not the usual way that a histogram is display graphically, where vertical bars are drawn to indicate the number of counts for each counted option. So, in this part of the problem, you should write a function called create_histogram_graph(array, width, height) which will use PGL to create a histogram GCompound.

The array parameter represents the same input array as from Part B (or the returned output from Part A),
The width and height parameters represent the desired size of the GCompound. You will need to use these values to figure out how wide and tall each of your histogram rectangles should be, depending on the number of counted values and the respective counts.

The function should return a GCompound object that contains filled GRect objects arranged to produce a traditional vertical bar graph histogram, where the height of a particular box reflects the proportional number of items in that index in the histogram array. The scaling of the bars should be chosen so that the largest bar in the graph completely fills the desired height, and all the bars arranged next to one another should completely fill the desired width. The reference point of the GCompound should be the upper left corner.

To illustrate how this part should work, it may help to consider the following simple test program, which is included in the code template:

def test_create_histogram_graph():
    WIDTH, HEIGHT = 800, 600
    gw = GWindow(WIDTH, HEIGHT)
    PI_DIGITS = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 8, 9, 7, 9]
    array = create_histogram_array(10, PI_DIGITS)
    graph = test_create_histogram_graph(array, WIDTH, HEIGHT)
    gw.add(graph)

which should display the following graph so that it fills the graphics window:

A `PI_DIGITS` traditional histogram. Note how the width of each of the bars is chosen so that the bars evenly fit within the desired width, and how the vertical scaling of the bars is such that the entry with the highest count (in this case, 5 with a count of 4) fills the desired height.

Note that because create_histogram_graph just returns to you a GCompound, if you made 4 of them with half the width and height of the window, you could also display multiple histograms across the screen by adding them at the correct coordinates:

Since your function just returns a `GCompound`, you could create 4 of them at half the width and height and display them all at once (by adding them at the correct positions)!

Problem 2

A magic square is a two-dimensional array of integers in which the rows, columns, and diagonals all add up to the same value. One of the most famous magic squares appears in the 1514 engraving Melencolia I by Albrecht Dürer shown below, in which a 4x4 magic square appears in the upper right, just under the bell. In Dürer’s square, all four rows, all four columns, and both diagonals add up to 34.

The *Melencolia I* by Albrecht Dürer, in which a magic square is visible in the upper right, just under the bell.

A more familiar example is the following 3x3 magic square, in which each of the rows, columns, and diagonals add up to 15, as shown:

Write a predicate function called is_magic_square that takes a two-dimensional array of integers and then tests whether that array of integers forms a magic square. The square could be of any size and the rows, columns, and diagonals could sum to any value. Your function should return True if the array forms a magic square, or False if it does not. Thus your function should also return False if the provided two-dimensional array is not square (for instance, if it is a 4x3 array).

Tip

This problem is prime for some good use of decomposition, as you need to check several different things in order to establish if a given square is magic. Consider writing a function to check each, and then stitching them all together to check if the square is magic!